package com.cb2.algorithm.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/combination-sum/">组合总和(Combination Sum)</a>
 * <p>给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。</p>
 * <p>candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 </p>
 * <p>对于给定的输入，保证和为 target 的不同组合数少于 150 个。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：candidates = [2,3,6,7], target = 7
 *      输出：[[2,2,3],[7]]
 *      解释：
 *          2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
 *          7 也是一个候选， 7 = 7 。
 *          仅有这两种组合。
 *
 * 示例 2：
 *      输入: candidates = [2,3,5], target = 8
 *      输出: [[2,2,2,2],[2,3,3],[3,5]]
 *
 * 示例 3：
 *      输入: candidates = [2], target = 1
 *      输出: []
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *  <ul>
 *      <li>1 <= candidates.length <= 30</li>
 *      <li>2 <= candidates[i] <= 40</li>
 *      <li>candidates 的所有元素 互不相同</li>
 *      <li>1 <= target <= 40</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @see LC0039CombinationSum_M 组合总和(Combination Sum)
 * @see LC0040CombinationSum_II_M 组合总和 II(Combination Sum II)
 * @see LC0216CombinationSum_III_M 组合总和 III(Combination Sum III)
 * @see LC0377CombinationSum_IV_M 组合总和 IV(Combination Sum IV)
 * @since 2025/2/12 11:55
 */
public class LC0039CombinationSum_M {
    static class Solution {
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            List<List<Integer>> resList = new ArrayList<>();
            backtracking(candidates, target, 0, new ArrayList<>(), resList);
            return resList;
        }

        /**
         * 查找符合条件的数
         *
         * @param candidates 候选数组
         * @param startIdx   搜索起点
         * @param target     每减去一个元素，目标值变小
         * @param path       路径集
         * @param resList    结果集列表
         */
        private void backtracking(int[] candidates, int target, int startIdx, List<Integer> path, List<List<Integer>> resList) {
            // target==0，找到一组，进行汇总
            if (target == 0) {
                resList.add(new ArrayList<>(path));
                return;
            }
            for (int i = startIdx; i < candidates.length; i++) {
                // 剪枝，因为候选数组是无序的，不能直接return。
                if (candidates[i] > target) {
                    continue;
                }
                path.add(candidates[i]);
                // 每一个元素可以重复使用，下一轮搜索的起点依然是 i
                backtracking(candidates, target - candidates[i], i, path, resList);
                path.remove(path.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printListListInteger(solution.combinationSum(new int[]{2, 3, 6, 7}, 7));
        Printer.printListListInteger(solution.combinationSum(new int[]{2, 3, 5}, 8));
        Printer.printListListInteger(solution.combinationSum(new int[]{2}, 1));
        Printer.printListListInteger(solution.combinationSum(new int[]{8, 7, 4, 3}, 11));
    }
}
